/*

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


执行用时 :4 ms, 在所有 C++ 提交中击败了94.98%的用户
内存消耗 :7.6 MB, 在所有 C++ 提交中击败了100.00%的用户

复杂度分析：
时间O(n),空间O(n)

大神讲的DP算法确实精彩，实现的也巧妙，自己写起来还是遇到了不少坑，附上讲解


Algorithm：
动态规划的题目一般分成三步：
1、确定状态，也就是你的答案表是存什么答案的。
2、确定状态转移方程，也就是怎么将你的答案表填满，换句话说，就是一些表达式。
3、确定边界情况，什么情况下有可能越界，要单独判断考虑（有可能无边界情况）。
有兴趣的话可以看一下动态规划经典例题 Leetcode-10-正则表达式匹配.

状态
dp[i] 表示以下标 i 为字符结尾的最长有效字符串的长度

状态转移方程
以 ( 结尾的子字符串不考虑，因为不可能构成合法括号

if s[i] == ')'
s[i - 1] == '('，也就是字符串形如 “……()”，我们可以推出：
dp[i] = dp[i − 2] + 2。
因为结束部分的 "()" 是一个有效子字符串，并且将之前有效子字符串的长度增加了 2.
s[i - 1] == ')'，也就是字符串形如 “.......))”，我们可以推出：
if s[i - dp[i - 1] - 1] == '('，dp[i] = dp[i − 1] + dp[i − dp[i − 1] − 2] + 2。
因为如果倒数第二个 )是一个有效子字符串的一部分（记为subs），我们此时需要判断 subs 前面一个符号是不是 ( ，如果恰好是(，我们就用 subs 的长度(dp[i - 1)加上 2 去更新 dp[i]。除此以外，我们也会把子字符串 subs 前面的有效字符串的长度加上，也就是 dp[i − dp[i − 1] − 2].
边界情况
i - 2 有可能小于零越界了，这种情况下就是只有 () ，前面记为 0 就好了.
i - dp[i - 1] - 1 和 i - dp[i - 1] - 2 都可能越界，越界了当成 0 来计算就可以了.

作者：Streetlight
链接：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/dong-tai-gui-hua-san-bu-zou-kan-liao-hen-ming-bai-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
#include <stack>
using namespace std;

class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> dp(s.size());
        int maxLen = 0;
        for ( int i = 1; i < s.size(); i++) {	//别他妈自作聪明的把i的类型改为unsigned int型，下面与int型运算时会出错，他妈的
            if (s[i] == ')') {					//警告就警告吧
                if (s[i - 1] == '(')  dp[i] = (i-2>=0?dp[i - 2]:0) + 2;		//注意边界条件
                else if (i - dp[i - 1] - 1 >= 0 && s[i-dp[i-1]-1] == '(' ) {
                    dp[i] = (i-1 >= 0 ? dp[i-1]:0) + ((i-dp[i-1]-2) >= 0 ?dp[i-dp[i-1]-2]:0) + 2;
                }
            }
            maxLen = maxLen > dp[i] ? maxLen : dp[i];
        }
        return maxLen;
    }
};
int main(int argc, char const* argv[]) {
    Solution s;
    string a = ")()()())";
    //string b = "cb";
    cout<<s.longestValidParentheses(a)<<endl;	
    return 0;
}
